/**
 * Внутренний итератор дерева.
 * Используется для поиска элементов, подсчёта количества элементов и т.п.
 * Хранит информацию о посещённых элементах.
 * <br/>
 * Содержит указатель на корень дерева и на текущий элемент.
 * Может работать неправильно, если между получениями следующего элемента
 * вызывается метод добавления или удаления элементов.
 * <br/>
 * Является небезопасным в многопоточный среде.
 */

#ifndef _INNERTREEITERATOR_H
#define	_INNERTREEITERATOR_H

#include <cassert>
#include <list>
#include <map>
#include "common/TreeAllocator.h"
#include "conf.h"
#include "Tree.h"
#include "TreeNode.h"

namespace etu {
namespace tree {

template <typename T> class Tree;

template <typename T>
class InnerTreeIterator {

public:
	typedef typename std::list<TreeNode<T> *,
                class common::TreeAllocator<TreeNode<T>* > > NodeList;
	typedef typename NodeList::iterator NodeListIterator;
	typedef typename std::map<TreeNode<T> *, NodeList > NodeStates;

private:
    friend class Tree<T>;

    TreeNode<T>* root;
    TreeNode<T>* currentNode;

    NodeStates nodeStates;

public:

    /**
     * Создание итератора для заданного дерева
     * @param tree дерево
     */
    InnerTreeIterator(const Tree<T>& tree) {
        this->root = this->currentNode = this->getTreeRoot(tree);
        this->goToFirst();
    }

    /**
     * Конструктор копирования
     */
    InnerTreeIterator(const InnerTreeIterator& orig) {
        this->currentNode = orig.currentNode;
        this->root = orig.root;
    }

    /**
     * Деструктор
     */
    virtual ~InnerTreeIterator() {
        //
    }

    /**
     * Переход к первому элементу.
     * Текущим элементов становится корень дерева.
     * Информация о посещённых элементах очищается.
     */
    virtual void goToFirst() {
        this->currentNode = this->root;
        this->nodeStates.clear();

        this->bypassNode(this->currentNode);
    }

    /**
     * Получение текущего элемента без перехода к следующему.
     * @return текущий элемент дерева
     */
    virtual TreeNode<T>* getCurrentNode() const {
        return this->currentNode;
    }

    /**
     * Получение следующего элемента в дереве.
     * @return следующий элемент; NULL, если больше нет элементов
     */
    virtual TreeNode<T>* next() {
        TreeNode<T>* ret = this->currentNode;

        if(this->currentNode != NULL) {
            this->currentNode = this->nextNode();
        }

        return ret;
    }

private:

    /**
     * Поиск следующего элемента в дереве. Обновление истории посещённых элементов дерева.
     * @return следующий элемент; NULL, если больше нет элементов
     */
    virtual TreeNode<T>* nextNode() {
        TreeNode<T>* ret = this->searchNotBypassedNode();

        if(ret != NULL) {
            this->bypassNode(ret);
        }

        return ret;
    }

    /**
     * Проходит по всем элементам map и ищет первую непосещённую ноду
     * @return непосещённая нода или NULL, если таких нет
     */
    virtual TreeNode<T>* searchNotBypassedNode() const {
        TreeNode<T>* ret = NULL;
        typename NodeStates::const_iterator it;

        for(it = this->nodeStates.begin(); it != this->nodeStates.end(); it++) {
            if((* it).second.size() > 0) {
                ret = (* (* it).second.begin());
                break;
            }
        }

        return ret;
    }

    /**
     * Совершаем обход ноды, то есть делаем её текущей, заносим её в map,
     * удаляя при этом её в списке непосещённых нод других элементов map
     * @param node нода
     */
    virtual void bypassNode(TreeNode<T>* node) {
        #ifdef __DEBUG__
        assert(!this->isNodeBypassed(node));
        #endif

        this->updateBypassedNodeState(node);

        NodeList notBypassedNodes;

        NodeList* parents = node->getParents();
        NodeList* childs = node->getChilds();
        NodeListIterator it;

        for(it = parents->begin(); it != parents->end(); it++) {
            if(!this->isNodeBypassed(* it)) {
                notBypassedNodes.push_back(* it);
            }
        }

        for(it = childs->begin(); it != childs->end(); it++) {
            if(!this->isNodeBypassed(* it)) {
                notBypassedNodes.push_back(* it);
            }
        }

        delete childs;
        delete parents;

        this->nodeStates.insert(std::make_pair<TreeNode<T> *,
        		NodeList >(node, notBypassedNodes));
    }

    /**
     * Удаляет в map в списке непосещённых нод других элементов заданную ноду
     * @param node нода
     */
    virtual void updateBypassedNodeState(TreeNode<T>* node) {
    	typename NodeStates::iterator it;

        for(it = this->nodeStates.begin(); it != this->nodeStates.end(); it++) {
            (* it).second.remove(node);
        }
    }

    /**
     * Проверка, была ли эта нода посещена
     * @param node нода
     * @return true, если нода была посещена; иначе false
     */
    virtual bool isNodeBypassed(TreeNode<T>* node) const {
        bool ret = false;
        typename NodeStates::const_iterator it;

        for(it = this->nodeStates.begin(); it != this->nodeStates.end(); it++) {
            if((* it).first == node) {
                ret = true;
                break;
            }
        }

        return ret;
    }

    /**
     * Получение корня для конкретного дерева.
     * Используется для доступа к закрытым элементам класса Tree.
     * @return корень дерева; NULL, если дерево не содержит узлов
     */
    TreeNode<T>* getTreeRoot(const Tree<T>& tree) const {
        return tree.root;
    }
};

}
}

#endif	/* _INNERTREEITERATOR_H */
